package interview.linked;

/**
 * 入环点
 */
public class InCyclePoint {

    /**
     * 寻找入环点
     * @param node 开始节点
     * @return 返回入环节点
     */
    public static Node inCyclePoint(Node node){
        Node p1 = node;
        Node p2 = node;
        //找到首次相遇的节点
        while(p1 != null && p2 != null){
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) break;
        }
        //p1重置为开始节点 两个节点每一次推动一个 再一次相遇就是入环节点
        while(true){
            p1 = node;
            p1 = p1.next;
            p2 = p2.next;
            if (p1 == p2) return p1;
        }
    }
}
